package h0911;

import java.util.ArrayList;
import java.util.List;

public class RestoreIPAddresses {
    public static void main(String[] args) {
        RestoreIPAddresses addresses = new RestoreIPAddresses();
        String s = "25525511135";
        List<String> list = addresses.restoreIpAddresses(s);
        System.out.println(list);
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() < 4 || s.length() > 12) {
            return res;
        }
        backTrack(res, new ArrayList<>(), s, 0);
        return res;
    }

    private void backTrack(List<String> res, List<String> current, String s, int start) {
        if (current.size() == 4) {
            if (start == s.length()) {
                res.add(String.join(".", current));
            }
            return;
        }
        for (int i = 1; i <= 3; i++) {
            if (start + i > s.length()) {
                break;
            }
            if (isValid(s, start, start + i)) {
                String temp = s.substring(start, start + i);
                current.add(temp);
                //注意这里回溯的时候是start+i
                backTrack(res, current, s, start + i);
                current.remove(current.size() - 1);
            }
        }
    }

    private boolean isValid(String s, int start, int end) {
        String segment = s.substring(start, end);
        if (end - start > 1 && segment.startsWith("0")) {
            return false;
        }
        int value = Integer.parseInt(segment);
        return value >= 0 && value <= 255;
    }
}
